W14. Matrix Dynamics and DFT

Author

Salman Ahmadi-Asl

Published

April 24, 2026

1. Theory

1.1 Matrix Exponentials and Linear Dynamic Systems

A first-order linear system of differential equations has the form

where is a constant matrix and is the state vector. This is the matrix version of the scalar equation , whose solution is . The same idea works for matrices, but the exponential must be interpreted through its power series:

The solution of the system is

This formula is not just notation. Differentiating the power series term by term gives

so , and at we have , hence .

When is diagonalizable, matrix exponentials are easiest to compute through eigenvalues and eigenvectors. If

then

Thus each eigenvector direction evolves independently, and the corresponding eigenvalue controls the growth or decay rate in that direction.

1.2 Stability from Eigenvalues, Trace, and Determinant

For a two-dimensional linear system , the eigenvalues of determine whether solutions grow, decay, rotate, or combine these behaviors.

If both eigenvalues have negative real parts, all solutions near the origin decay toward the origin; the system is stable. If at least one eigenvalue has positive real part, there are solutions that grow away from the origin; the system is unstable. If eigenvalues are complex, their real part controls growth or decay while their imaginary part produces rotation.

For a matrix

the trace and determinant are

The characteristic polynomial is

so the eigenvalues are

The quantity is the discriminant. It separates real eigenvalues from complex eigenvalues:

  • if , the eigenvalues are real and distinct;
  • if , the eigenvalues are repeated;
  • if , the eigenvalues are complex conjugates with real part .

The determinant gives the product of the eigenvalues, and the trace gives their sum. Therefore, if , the eigenvalues have opposite signs, so the system is unstable. If and , both real eigenvalues are negative or both complex eigenvalues have negative real part, so the system is stable. If and , the system is unstable.

1.3 Nilpotent Matrices and Finite Exponential Series

A matrix is nilpotent if some power of it is the zero matrix. The simplest nonzero case is . Then all higher powers also vanish:

The infinite matrix exponential series collapses to a finite expression:

This is important because it shows that matrix exponentials are not always hard to compute. The structure of the matrix determines the method. Diagonalizable matrices are handled by eigenvectors; nilpotent matrices are handled by the power series directly.

1.4 Fourier Analysis and the Discrete Fourier Transform

Fourier analysis is based on the idea that complicated signals can be decomposed into simple oscillations. In continuous mathematics, this leads to the Fourier transform

Computers, however, work with finite lists of samples, not continuous functions. If is a vector of samples, the Discrete Fourier Transform (DFT) produces frequency components:

The DFT is used in audio processing, image compression, medical imaging, telecommunications, numerical differential equations, quantum mechanics, and many other fields. Its power comes from representing a signal in a frequency basis rather than the original time or sample basis. In that frequency basis, periodic structure, oscillations, and repeated patterns often become easier to detect, filter, compress, or solve with.

For deeper study of how the DFT leads to fast algorithms, the standard reference mentioned in the lecture is Strang’s Linear Algebra and Its Applications, especially the FFT chapter.

1.5 Roots of Unity

The DFT is built from roots of unity. The -th roots of unity are the complex numbers satisfying

They are

They lie evenly spaced on the unit circle in the complex plane. For example, when , the roots are eight equally spaced points: , a first-quadrant diagonal point, , a second-quadrant diagonal point, , a third-quadrant diagonal point, , and a fourth-quadrant diagonal point. This geometric picture matters because the powers of rotate by equal angles and eventually return to .

In the DFT convention used here, we define the primitive root

Then , and all powers repeat periodically:

There are also two useful symmetry rules:

and

The key algebraic identity is the finite geometric sum:

This identity is the reason the Fourier matrix is orthogonal in the complex sense.

1.6 The Fourier Matrix

The DFT can be written as a matrix-vector multiplication:

The normalized Fourier matrix is

where . Written out,

The factor is a normalization. With this factor, preserves lengths and becomes a unitary matrix. Some sources omit the normalization; then the inverse contains a factor instead. This convention issue is common: the unnormalized DFT, the normalized DFT, and the inverse DFT may distribute the constants differently, but they encode the same transformation.

For example, when , , so

1.7 Conjugate Fourier Matrix and Inverse DFT

The conjugate Fourier matrix is obtained by conjugating every entry of :

The conjugate transpose is the inverse of the normalized Fourier matrix:

Therefore, if is the DFT, then the original samples are recovered by

Component-wise,

This is the inverse DFT under the symmetric normalization convention.

For , the conjugate Fourier matrix is

It differs from by changing to and to .

1.8 Orthogonality and Unitarity of the Fourier Matrix

In complex vector spaces, orthogonality is measured with the Hermitian inner product, which uses conjugation. The columns of form an orthonormal basis of :

To see why, compute the inner product of column and column :

If , every term is , so the sum is and the result is . If , the sum is a finite geometric series with ratio not equal to , and it equals . Hence

where is the Kronecker delta. This proves that is unitary. Since , the rows are also orthonormal:

One subtle point is that the Fourier matrix is symmetric, , because . But it is not generally Hermitian, because except in very small special cases.

Several consequences follow immediately from unitarity. First, , because

Second, all eigenvalues of a unitary matrix have absolute value . For the Fourier matrix, the stronger identity implies that its eigenvalues must be fourth roots of unity, so they belong to the set , with multiplicities depending on .

1.9 Powers of the Fourier Matrix

The Fourier matrix has a remarkable connection with permutations. For the normalized DFT matrix, reverses indices modulo :

Thus is a permutation matrix , and

For , this means

The permutation fixes indices and and swaps indices and . This property is often a useful shortcut in computations involving repeated Fourier transforms.

The relationship with the conjugate matrix also explains the column permutation in the unnormalized convention. Since , conjugating the Fourier matrix replaces column by column . Therefore for the permutation .

2. Definitions

  • Matrix exponential: The matrix function , used to solve .
  • Linear dynamic system: A differential equation system of the form , where the future state is determined by a matrix acting on the current state.
  • Stable system: A system whose solutions decay toward the equilibrium; for a linear system this occurs when all eigenvalues have negative real parts.
  • Unstable system: A system with at least one eigenvalue having positive real part, so some solutions grow away from equilibrium.
  • Trace: The sum of diagonal entries of a square matrix; for a matrix it equals the sum of eigenvalues.
  • Determinant: A scalar measuring signed area/volume scaling; for a matrix it equals the product of eigenvalues.
  • Nilpotent matrix: A matrix such that for some positive integer .
  • Fourier analysis: The study of representing signals or functions as sums of complex exponentials.
  • Continuous Fourier Transform: The integral transform , which represents a continuous function by frequencies.
  • Discrete Fourier Transform (DFT): The transformation from samples to frequency components, computed by sums involving roots of unity.
  • Root of unity: A complex number satisfying for some positive integer .
  • Primitive -th root of unity: A root whose powers generate all roots of unity; here .
  • Fourier matrix: The matrix with entries , representing the normalized DFT.
  • Conjugate Fourier matrix: The entrywise conjugate , with entries .
  • Inverse DFT: The operation that reconstructs the sample vector from its frequency components; under normalized convention it is multiplication by .
  • Orthonormal basis: A basis whose vectors all have norm and are pairwise orthogonal.
  • Unitary matrix: A complex square matrix satisfying , equivalently .
  • Conjugate transpose: The matrix obtained by transposing and conjugating every entry.
  • Kronecker delta: The symbol , equal to if and otherwise.
  • Permutation matrix: A matrix obtained by permuting the columns of the identity matrix; multiplying by it permutes vector components.

3. Formulas

  • Matrix exponential series: .
  • Solution of a linear system: for and .
  • Diagonalizable matrix exponential: If , then .
  • Trace-determinant characteristic polynomial: , where and .
  • Eigenvalues from trace and determinant: .
  • Nilpotent exponential for : .
  • Continuous Fourier Transform: .
  • DFT component formula: .
  • Primitive root of unity: .
  • Periodicity of roots: and .
  • Conjugation of roots: .
  • Fourier matrix entries: for .
  • Geometric sum of roots of unity: if , and otherwise.
  • Fourier unitarity: .
  • Inverse Fourier matrix: .
  • Inverse DFT formula: .
  • Column orthogonality identity: .
  • Row orthogonality identity: .
  • Fourier determinant magnitude: for the normalized Fourier matrix.
  • Fourier square permutation: and .
  • Possible Fourier eigenvalues: If , then every eigenvalue of is in .

4. Practice

4.1 Eigenvalues, Eigenvectors, and Matrix Exponential (Lab 11, Task 1)

Find the eigenvalues, eigenvectors, and for

Click to see the solution

Key Concept: Diagonalize using eigenvectors. Once , the matrix exponential is .

Step 1 — Find the eigenvalues.

Compute the characteristic polynomial:

Factor:

Therefore,

Step 2 — Find eigenvectors.

For , solve :

Thus , so one eigenvector is

For , solve :

The equation is , so . One eigenvector is

Step 3 — Build the diagonalization.

Let

The inverse of is

because .

Step 4 — Exponentiate the diagonal matrix.

Therefore,

Multiply:

Answer:

and

4.2 Solve a Linear Differential Equation System (Lab 11, Task 2)

Solve

where

Click to see the solution

Key Concept: Use . The matrix exponential was found in Task 1.

From Task 1,

Multiply by the initial vector:

Compute each component explicitly:

Thus

Check the initial condition:

Interpretation: The sum stays constant. The difference decays to , so both components approach .

Answer:

4.3 Matrices for Three Stability Regions (Lab 11, Task 3)

Find a matrix to illustrate each stability region:

and ; and ; complex eigenvalues with real part .

Click to see the solution

Key Concept: We may choose simple matrices whose eigenvalues are obvious. Diagonal matrices give prescribed real eigenvalues directly, and rotation-scaling blocks give complex eigenvalues.

(a) One negative and one positive eigenvalue.

Choose

Because this matrix is diagonal, its eigenvalues are the diagonal entries:

This lies in the region , because . The system is unstable because the positive eigenvalue gives a growing direction.

(b) Two positive real eigenvalues.

Choose

Again the eigenvalues are read from the diagonal:

Here and , so both eigenvalues are positive and solutions grow away from the origin.

(c) Complex eigenvalues with positive real part.

A standard matrix with eigenvalues is

Choose and :

The characteristic polynomial is

Setting it equal to zero gives

So the eigenvalues are and , both with real part . The system spirals outward and is unstable.

Answer: One possible set is

4.4 Stability Changes from Trace and Determinant (Lab 11, Task 4)

From their trace and determinant, at what time do the following matrices change between stable with real eigenvalues, stable with complex eigenvalues, and unstable?

Click to see the solution

Key Concept: For a matrix, use , , and the discriminant . Stability depends on the sign of the real parts of eigenvalues; real versus complex depends on .

Matrix .

Compute trace and determinant:

The discriminant is

Now classify by .

  • If , then . The eigenvalues have opposite signs, so the system is unstable.
  • If , then . One eigenvalue is zero; this is the boundary between opposite-sign real eigenvalues and complex eigenvalues.
  • If , then and , so eigenvalues are complex. Their real part is , so they are purely imaginary, not asymptotically stable.

Therefore changes type at

It moves from unstable real eigenvalues () to purely imaginary complex eigenvalues (). Because always, it does not become stable with negative real part.

Matrix .

Compute trace and determinant:

The discriminant is

So the eigenvalues are complex for every real . In fact,

The real part is . Therefore:

  • if , both eigenvalues have negative real part, so the system is stable with complex eigenvalues;
  • if , eigenvalues are purely imaginary, , so this is the stability boundary;
  • if , both eigenvalues have positive real part, so the system is unstable with complex eigenvalues.

Thus changes stability at

Answer: changes eigenvalue type at ; it is unstable for and has purely imaginary eigenvalues for . changes stability at ; it is stable spiral for , neutral at , and unstable spiral for .

4.5 Exponential of a Nilpotent Matrix (Lab 11, Task 5)

The matrix has . Find from an infinite series. Check that the derivative of is .

Click to see the solution

Key Concept: If , then all powers for are zero. The infinite exponential series becomes finite.

First verify :

Use the power series:

Since , all terms after vanish:

Substitute :

Now check the derivative:

Compute :

Thus

Answer:

4.6 Powers of the Fourier Matrix from a Column Permutation (Lab 11, Task 6)

Find a permutation of the columns of that produces for the by Fourier matrix. Combine with to find and .

Click to see the solution

Key Concept: This problem uses the unnormalized Fourier matrix. Its entries are with and . The conjugate entries are .

For column of , the entries are

This is the same as column of , with indices understood modulo . Therefore, to transform into , the permutation must send column to column .

In index form:

Thus is the reversal permutation modulo :

Since , multiply both sides on the right by :

Because , this returns from , as expected.

Now use the given identity

Since , substitute:

Therefore

Multiply on the right by :

Then

Normalized version: If the normalized Fourier matrix is , then

Answer: is the permutation . For the unnormalized Fourier matrix, and . For the normalized Fourier matrix, and .

4.7 Solve a Fourier System (Lab 11, Task 7)

Solve the by system if the right-hand sides are

Click to see the solution

Key Concept: The source problem uses the unnormalized Fourier matrix

For the unnormalized matrix, . Since is symmetric, this is .

We need solve

Thus

Now

Multiply:

Therefore

Check:

Answer:

4.8 The Fourier Matrix (Lecture 11, Example 1)

For , write the Fourier matrix explicitly and verify orthogonality.

Click to see the solution

Key Concept: Use and the normalized Fourier matrix formula .

For ,

The entries are

Because this matrix is real, . It is also symmetric, so . Check:

Answer:

and its columns are orthonormal because .

4.9 The Fourier Matrix (Lecture 11, Example 2)

For , write the Fourier matrix explicitly.

Click to see the solution

Key Concept: For , the primitive root is and powers are reduced modulo because .

Compute the root:

The Fourier matrix is

Since , we have . Therefore,

Answer:

4.10 The Fourier Matrix (Lecture 11, Example 3)

For , write the Fourier matrix explicitly.

Click to see the solution

Key Concept: Compute powers of and substitute them into .

For ,

Its powers are

Now fill the entries row by row:

Reduce powers modulo : , , and . Hence

As a concrete entry check,

Answer:

4.11 Compute the DFT of a Four-Point Vector (Lecture 11, Example 4)

Compute the DFT of using .

Click to see the solution

Key Concept: The DFT is the matrix-vector product .

Compute:

Only the first and third columns contribute:

Answer: The DFT of is itself:

4.12 Show that is a Permutation Matrix (Lecture 11, Example 5)

Show that is a permutation matrix for .

Click to see the solution

Key Concept: Applying the normalized Fourier transform twice reverses indices modulo . For , indices become .

Using

direct multiplication gives

This matrix is a permutation matrix because each row and each column has exactly one entry equal to , and all other entries are .

Its action on a vector is

So fixes components and and swaps components and .

Answer:

which is the permutation matrix for index reversal modulo .

4.13 Orthogonality of the Columns of (Lecture 11, Task 1)

Show that the columns of are orthogonal.

Click to see the solution

Key Concept: In , orthogonality uses the Hermitian inner product. That means we conjugate the entries of the first vector before multiplying.

Let the columns of be

For , we have

Check with :

Check with :

Check with :

Using conjugation,

Since and , this becomes

Because , we get

Each column also has norm ; for example,

Answer: The columns of are mutually orthogonal, and after the factor they are orthonormal. Hence .